#include <stdio.h>
//图的应用之最小生成树之克鲁斯卡尔算法
#define MAXSIZE 100
#define MAX 0x7fffffff  //int类型最大值
typedef char ElemType;
//图的声明
typedef struct 
{
    ElemType vertex[MAXSIZE];
    int edge[MAXSIZE][MAXSIZE];
    int vertex_num;
    int edge_num;
}mat_graph;
//图的创建
void creatgraph(mat_graph *g)
{
    g->vertex_num=9;
    g->edge_num=15;
    g->vertex[0]='A';
    g->vertex[1]='B';
    g->vertex[2]='C';
    g->vertex[3]='D';
    g->vertex[4]='E';
    g->vertex[5]='F';
    g->vertex[6]='G';
    g->vertex[7]='H';
    g->vertex[8]='I';
    int i,j;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<g->vertex_num;j++)
        {
            if(i==j)
            {
                g->edge[i][j]=0;
            }
            else
            {
                g->edge[i][j]=MAX;
            }
        }
    }
    //A-B A-F
    g->edge[0][1]=10;
    g->edge[0][5]=11;
    //B-C B-G B-I
    g->edge[1][2]=18;
    g->edge[1][6]=16;
    g->edge[1][8]=12;
    //C-D C-I
    g->edge[2][3]=22;
    g->edge[2][8]=8;
    //D-E D-G D-H D-I
    g->edge[3][4]=20;
    g->edge[3][6]=24;
    g->edge[3][7]=16;
    g->edge[3][8]=21;
    //E-F E-H
    g->edge[4][5]=26;
    g->edge[4][7]=7;
    //F-G
    g->edge[5][6]=17;
    //G-H
    g->edge[6][7]=19;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<i;j++)
        {
            g->edge[i][j]=g->edge[j][i];
        }
    }
}
//边的声明：因为这种算法是先找最小权值边，再连顶点
typedef struct 
{
    int begin; //顶点下标(0~8)
    int end;   //顶点下标(0~8)
    int weight; //两个顶点连成的边的权值
}Edge;
void swap(Edge *e1,Edge *e2)
{
    Edge a=*e1;
    *e1=*e2;
    *e2=a;
}
void sortedge(Edge *e,mat_graph *g)
{
    int i,j;
    for(i=0;i<g->edge_num;i++)
    {
        for(j=i+1;j<g->edge_num;j++)
        {
            if(e[i].weight>e[j].weight)
            {
                swap(&e[i],&e[j]); //交换
            }
        }
    }
}
int find(int parent[],int i)
{
    while(parent[i]>0)
    {
        i=parent[i]; 
    }
    return i;
}
void kruskal(mat_graph *g)
{
    //因为要找最小边所以要排序，那么用数组将所有边集合起来
    Edge e[g->edge_num];
    //给结构体数组赋值，begin是0~g->vertex_num-1，end是0~g->vertex_num-1，weight要与之对应
    //因为无向图边没有方向，所以只要edge数组对角线的一半
    int i,j,k=0; //用k代替循环
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=i+1;j<g->vertex_num;j++)  //赋值边数组右上角部分，使begin<end
        {
            if(g->edge[i][j]!=MAX)
            {
                e[k].begin=i;
                e[k].end=j;
                e[k].weight=g->edge[i][j];
                k++;
            }
        }
    }
    //排序：从小到大
    sortedge(e,g);
    int parent[MAXSIZE]={0}; //用来存放边的关系，类似普里姆算法中的vex_index数组
    int n,m;
    for(i=0;i<g->edge_num;i++)
    {
        n=find(parent,e[i].begin);//4 //2 //0 //0(返回1) //1(返回5) //1(返回8) //3 //5(返回6) //1(返回6)
        m=find(parent,e[i].end);  //7 //8 //1 //5(返回5) //8(返回8) //6(返回6) //7 //6(返回6) //2(返回6)
        if(n!=m)  //当都返回6时就不会进入打印，巧妙地避开形成环
        {
            parent[n]=m;
            //printf("(%c %c)",g->vertex[m],g->vertex[n]);//HE IC BA FB(这里是指ABF三点连线)，所以不要这样打印
            printf("(%c %c)",g->vertex[e[i].begin],g->vertex[e[i].end]);
        }
    }
}
int main()
{
    mat_graph g;
    creatgraph(&g);
    kruskal(&g);
    return 0;
}
//输出:(E H)(C I)(A B)(A F)(B I)(D H)(B G)(G H)
//过程中存在的问题：在赋值边结构体数组时，若赋值的是边数组左下角部分为什么会输出GF，会出错？
//这种情况是begin>end，那这样的话n,m赋值就要反过来：m=find(parent,e[i].begin); n=find(parent,e[i].end);
//若不反过来，则如下：
//7 //8 //1 //5 //8(返回2) //6  //7(返回4) //6(返回1)
//4 //2 //0 //0 //1        //1  //3       //5       这里由于n!=m而形成环
//这种算法的巧思就在于要保证begin<end，才会巧妙避开环